package binarytree;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉搜索树的最近公共祖先
 */
public class LowestCommonAncestorOfABinarySearchTree {

  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    return null;
  }


  /**
   * 思路1：<br>
   *     使用两个 List 分别存储，root 到 p 以及 q 所需要经过的节点。<br>
   *     遍历两个 List ，遇到 p q 都经过的节点则记录一下，最后的那个节点则是最近的公共祖先，<br>
   *         要使得两个节点有公共祖先，则这两个节点到 root 节点一定存在部分相同的路径
   *
   */
  class Solution1 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      List<TreeNode> pathFromRootToP = getPath(root, p);
      List<TreeNode> pathFromRootToQ = getPath(root, q);
      TreeNode ancestor = null;
      for (int i = 0; i < pathFromRootToP.size() && i < pathFromRootToQ.size(); ++i) {
        if (pathFromRootToP.get(i) == pathFromRootToQ.get(i)) {
          ancestor = pathFromRootToP.get(i);
        } else {
          break;
        }
      }
      return ancestor;
    }

    public List<TreeNode> getPath(TreeNode root, TreeNode target) {
      List<TreeNode> path = new ArrayList<>();
      TreeNode node = root;
      while (node != target) {
        path.add(node);
        if (target.val < node.val) {
          node = node.left;
        } else {
          node = node.right;
        }
      }
      path.add(node);
      return path;
    }
  }

  /**
   * 思路2：<br>
   *     刚好找到  p.val < ancestor.val < q.val （假设q.val > p.val）的这个节点，就是p, q 节点的最近公共祖先，因此我们需要从 root 节点开始不断移动，直到满足这个条件<br>
   *     在移动过程中有如下的情况。<br>
   *     &nbsp    1. 一开始 ancestor 是从 root 节点出发的。所以 ancestor.val >= q.val > p.val 。<br>
   *             如果遇到 ancestor = q.val 的情况，那么就已经成立了，返回当前 ancestor 节点。<br>
   *     &nbsp    2.  ancestor.val > q.val > p.val，那么说明 q p 在 ancestor 的左子树，<br>
   *             所以 ancestor 移动到 ancestor.left 节点，代码中这样进行表述：ancestor = ancestor.left; <br>
   *     &nbsp   3.  在移动过程中，可能 p, q 节点都在当前 ancestor 节点的右子树，所以可能会出现 q.val > p.val > ancestor.val 的情况，<br>
   *             这个时候，ancestor 需要向其右子树移动，反映到代码中则是 ancestor = ancestor.right;<br>
   *     &nbsp  4.  当出现 q.val > ancestor.val >= p.val时，条件成立，返回当前 ancestor 节点。<br>
   *
   *
   *
   */
  class Solution2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      TreeNode ancestor = root;
      //刚好找到 leftVal < val < rightVal这个节点
      while (true) {
        if (p.val < ancestor.val && q.val < ancestor.val) {
          ancestor = ancestor.left;
        } else if (p.val > ancestor.val && q.val > ancestor.val) {
          ancestor = ancestor.right;
        } else {
          break;
        }
      }
      return ancestor;
    }
  }
}
